/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * @since 2023-08-27 11:17
 */
public class _005最长回文串 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
    }
    public static String longestPalindrome(String s) {
        int maxLen = 0, start = 0;
        int len;
        for(int i = 0; i < s.length(); i++){
            len = getLen(s, i, i) - 1;
            if(len > maxLen){
                maxLen = len;
                start = i - len/2;
            }
            len = getLen(s, i, i + 1);
            if(len > maxLen){
                maxLen = len;
                start = i - len/2 + 1;
            }
        }
        return s.substring(start, start + maxLen);
    }
    // s[left-right] 向两端扩展得到最长的回文串长度
    public static int getLen(String s, int left, int right){
        int cnt = 0;
        while(left >= 0 && right < s.length()){
            if(s.charAt(left--) != s.charAt(right++)){
                return cnt;
            }
            cnt += 2;
        }
        return cnt;
    }
}
